package 动态规划;

public class 杨辉三角 {


    public static void main(String[] args) {
        int[] arr = {1,3,5,4,5,6,4,3,2,1};
        System.out.println(yanghuiTriangle(arr));
    }

    public static int yanghuiTriangle(int[] arr){
        int length = arr.length;
        if (length == 1){
            return arr[0];
        }
        //计算层高
        int n = (int) ((-1 + Math.sqrt(1 + 8 * length)) / 2);
        //避免最后一层不满的情况
        if (n * (n + 1) / 2 < length){
            n = n + 1;
        }

        //定义一个结果数组
        int[] result = new int[length];
        //初始化数组
        result[0] = arr[0];
        for (int i = 2; i <= n; i++) {
            //从第一层开始,层层遍历
            for (int j = 0; j < n; j++) {
                //计算当前数字在数组中的下标
                int index = i * (i - 1) / 2 + j;
                if (index >= length){
                    break;
                }
                int right = index - i + 1;
                int left = index - i;
                if (j == 0){
                    result[index] = result[right] + arr[index];
                }else if (j == n-1){
                    result[index] = result[left] + arr[index];
                }else {
                    result[index] = Math.min(result[right], result[left]) + arr[index];
                }
            }
        }
        int lastBeginIndex = n * (n - 1) / 2;
        int min = Integer.MAX_VALUE;
        for (int i = lastBeginIndex; i < length; i++) {
            if (result[i] < min){
                min = result[i];
            }
        }

        return min;
    }
}
